class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mysort(nums,0,nums.size()-1,tmp);
        return nums;
    }

    void mysort(vector<int>& nums,int left,int right,vector<int>& tmp)
    {
        if(left>=right) return;
        int mid=left+(right-left)/2;
        //[left,mid]  [mid+1,right]
        mysort(nums,left,mid,tmp);
        mysort(nums,mid+1,right,tmp);

        int cur1=left;
        int cur2=mid+1;
        int i=0;
        while(cur1<=mid&&cur2<=right)
        {
            if(nums[cur1]>nums[cur2])
            {
                tmp[i++]=nums[cur2++];
            }
            else if(nums[cur1]<nums[cur2])
            {
                tmp[i++]=nums[cur1++];
            }
            else
            {
                tmp[i++]=nums[cur2++];
            }
        }
        while(cur1<=mid)
        {
            tmp[i++]=nums[cur1++];
        }
         while(cur2<=right)
        {
            tmp[i++]=nums[cur2++];
        }
        for (int k = 0; k < i; ++k) {
            nums[left + k] = tmp[k];
        }
    }
};
